/**
 * Alipay.com Inc.
 * Copyright (c) 2004-2021 All Rights Reserved.
 */
package primary.primary0;

/**
 * S0045跳跃游戏II，好像差不多
 * 注意如果能走到最后的话，中间一定是不存在某个点是不可访问到的
 */
public class S0055跳跃游戏 {

    /**
     * 5,从前到后遍历，
     * 这个其实也是递推了属于是
     * 每个点把它能到达的所有位置canvisit置为true，然后访问下一个点，如果下一个点是false的话意味着走不下去了，整体为false
     */
    class Solution {
        public boolean canJump(int[] nums) {
            boolean[] canvisit = new boolean[nums.length];
            canvisit[0] = true;
            for(int i = 0; i < nums.length; i++){
                if(!canvisit[i]){
                    return false;
                }
                for(int j = i; j <= i + nums[i] && j < nums.length; j++){
                    canvisit[j] = true;
                }
            }
            return true;
        }
    }



    /**
     * 96
     * 从前往后, 看它能跳到的最远的地方, 每碰到一个点就更新一下
     * 确实，不必更新每个值能不能到，只需要维护一个最大值就行
     */
    public boolean canJump(int[] nums) {
        int base = 0;
        int totalLen = nums.length;
        for(int i = 0; i < totalLen; i++){
            // 可以跳到最后了
            if(base >= totalLen - 1) return true;
            // 防止中间就不可到达最后
            if(base == i && nums[i] == 0) break;
            // 更新能去的最远的地方
            base = Math.max(base, i + nums[i]);
        }
        return false;
    }

    /**
     * 反过来, 如果能到最后, 那么一定是通过某一个点到的最后,
     * 如果通过这个点到的最后, 那么这个点前面肯定也有点, 直到起点
     */
    public boolean canJump2(int[] nums) {
        int len = nums.length;
        int end = len - 1;
        for (int i = len - 2; i >= 0 ; i--) {
            if (nums[i] >= end - i) {
                // 这里的终点替换, 是没有损失的, 因为本来到最后的点就是可以到中间的所有点,
                // 现在到了这个点就可以到最后的点, 那么说明这两个目标是完全等价的
                end = i;
            }
        }
        return end == 0;
    }

}